package com.zhaopin.theswordreferstooffer;

import java.util.Objects;

/**
 * @author yin.peide
 * @date 2021-06-09 18:02
 * 面试题15: 链表中的倒数第k个节点
 */
public class Offer15 {


    public static void main(String[] args) {
        LinkedNode l5 = new LinkedNode(5);
        LinkedNode l4 = new LinkedNode(4);
        LinkedNode l3 = new LinkedNode(3);
        LinkedNode l2 = new LinkedNode(2);
        LinkedNode l1 = new LinkedNode(1);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        LinkedNode linkedNode = returnKNode(l1,6);
        if(Objects.nonNull(linkedNode)){
            System.out.println(linkedNode.value);
        }
        if(Objects.isNull(linkedNode)){
            System.out.println("链表为null");
        }



    }

    public static LinkedNode returnKNode(LinkedNode head,int k){
        if(Objects.isNull(head)){
            System.out.println("头结点为null");
            return null;
        }

        //k 应该数一个大于0 并且小于链表的长度值
        if(k <= 0){
            System.out.println("");
            return null;
        }



        //设置两个指针
        LinkedNode p1 = head;
        LinkedNode p2 = head;
        int i = 0;
        while (i < k-1){
            p1 = p1.next;
            if(Objects.isNull(p1)){
                System.out.println("不允许k > 链表长度");
                return null;
            }
            i ++ ;
        }

        //然后p1 移动到末尾,得到p2的节点就是倒数第k个节点
        while (Objects.nonNull(p1.next)){
             p1 = p1.next;
             p2 = p2.next;
        }
        return p2;
    }

}




class LinkedNode{
    int value;
    LinkedNode next;

    public LinkedNode(int value) {
        this.value = value;
    }
}
